﻿#define _CRT_SECURE_NO_WARNINGS

//力扣138：复制带随机指针的链表

//给你一个长度为 n 的链表，
//每个节点包含一个额外增加的随机指针 random ，
//该指针可以指向链表中的任何节点或空节点。
//构造这个链表的 深拷贝。 
//深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。
//新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，
//并使原链表和复制链表中的这些指针能够表示相同的链表状态。
//复制链表中的指针都不应指向原链表中的节点 。

//例如，如果原链表中有 X 和 Y 两个节点，
//其中 X.random-- > Y 。
//那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random-- > y 。
//返回复制链表的头节点。


//这道题的重点是在怎么处理random，拷贝的指针的random，怎么能找到拷贝过去的random所指的地址。
//因为新开辟的结点的地址之间没有关系，所以新开辟的结点不好找，即使一一遍历，也有可能有重复的结点

//思路
//1.copy结点链接在原结点的后面
//2.控制random   copy->random=cur->random->next;
//3.把拷贝结点解下来，恢复原链表

struct Node* copyRandomList(struct Node* head) 
{
    //1.copy结点链接在原结点的后面
    struct Node* cur = head;     //创建一个新指针，用来遍历链表
    while (cur)
    {
        struct Node* copy = (struct Node*)malloc(sizeof(struct Node));    //开辟一个新结点，用来当作复制原结点的结点
        copy->val = cur->val;            //深拷贝，就是完全复制链表，val next random完成保持一致  所以val肯定是要相等的。

        copy->next = cur->next;          //新开的结点放在原结点的后面，就相当于插入结点，如果不另创建一个结点，保存第二个结点的地址，
        cur->next = copy;                //那就得先把新结点，和第二个结点链接起来，然后再去链接新结点和第一个结点。

        cur = copy->next;                //之后让链表动起来，要把链表里所有的结点的拷贝都放在原结点的后面，链表的停止条件就是cur==NULL
    }
    //2.控制random   copy->random=cur->random->next; 
    cur = head;                           //控制random，先让cur回到head处
    while (cur)
    {
        struct Node* copy = cur->next;    //创建一个copy指针，指向拷贝的结点，因为把拷贝的结点都放在了原结点的后面，所以直接copy=cur->next
        if (cur->random == NULL)          //判断下，如果原结点的random是NULL，那拷贝过去的结点的random肯定也是NULL
            copy->random = NULL;
        else
        {
            copy->random = cur->random->next;  //random不是NULL的情况，就是copy->random=cur->random->next.
        }
        cur = copy->next;                   //还得让链表动起来，遍历链表
    }
    //3.把拷贝结点解下来，恢复原链表
    cur = head;                                 //先让cur回到head处
   // struct Node* copyHead, * copyTail = NULL;  这么写是错的
    struct Node* copyHead=NULL, * copyTail = NULL;  //把拷贝的结点解下来，就是相当于尾插到新链表，所以得创建copyHead，尾插要找尾，所以得创建copyTail，
   
    while (cur)                                 //停下来的条件依旧是cur==NULL
    {
        struct Node* copy = cur->next;          //先创建指针，指向要尾插的结点，把尾插后的下一个结点存起来
        struct Node* next = copy->next;

        if (copyTail == NULL)                   //尾插的时候，也是需要判断下，链表是不是NULL，尾插的是不是链表的第一个
        {
            copyTail = copyHead = copy;         //如果尾插的是第一个，那头结点就找到了，尾结点也跟着改变。
        }
        else
        {
            copyTail->next = copy;              //如果不是，那就尾插到tail->next处
            copyTail = copyTail->next;
        }
        cur->next = next;                       //恢复原来链表，把cur->next=next
        cur = cur->next;                        //更新cur,把next赋给cur   next就是cur->next
    }

    return copyHead;
}
